package 快速幂;

import java.util.Scanner;

public class Main {
    //给定 n组 ai,bi,pi，对于每组数据，求出 abiimodpi的值。
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        while (n-- > 0) {
            int a = in.nextInt();
            int b = in.nextInt();
            int p = in.nextInt();
            System.out.println(qmi(a, b, p));
        }
    }

    private static long qmi(long a, int b, int p) {
        long ret = 1 % p;//a=1,b=0,p=1;
        while (b > 0) {
            if ((b & 1) == 1) {
                ret = ret * a % p;
            }
            b >>= 1;
            a = a * a % p;
        }
        return ret;
    }
}
